export var MyCalendarThree = function () {
  this.tree = new SegmentTree()
}

/**
 * @param {number} start
 * @param {number} end
 * @return {number}
 */
MyCalendarThree.prototype.book = function (start, end) {
  this.tree.update([start, end - 1], 1)
  return this.tree.getRoot().v
}

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * var obj = new MyCalendarThree()
 * var param_1 = obj.book(start,end)
 */

class Node {
  constructor(range, left, right) {
    this.v = 0
    this.left = left || null
    this.right = right || null
    this.range = range
    this.add = 0
  }
}

class SegmentTree {
  constructor() {
    const range = [0, 10 ** 9]
    this.root = new Node(range, null, null)
  }

  getRoot() {
    return this.root
  }

  update(range, v, node = null) {
    const [l, r] = range
    if (l > r) return
    if (node === null) node = this.root
    const [nL, nR] = node.range
    const mid = (nL + nR) >> 1
    if (nL >= l && nR <= r) {
      node.v += v
      node.add += v
      return
    }
    // 动态开点，下传lazy
    this.pushdown(node)
    if (l <= mid) this.update(range, v, node.left)
    if (r > mid) this.update(range, v, node.right)
    this.pushup(node)
  }

  query(l, r, node = null) {
    if (l > r) return 0
    if (node === null) node = this.root
    const [nL, nR] = node.range
    const mid = (nL + nR) >> 1
    if (l <= nL && nR <= r) return node.v
    this.pushdown(node)
    let v = 0
    if (l <= mid) v = Math.max(v, this.query(l, r, node.left))
    if (r > mid) v = Math.max(v, this.query(l, r, node.right))
    return v
  }

  /**
   * 向上检索
   */
  pushup(node) {
    node.v = Math.max(node.left.v, node.right.v)
  }

  /**
   * 向下检索
   */
  pushdown(node) {
    const [l, r] = node.range
    const mid = (l + r) >> 1
    if (node.left === null) node.left = new Node([l, mid], null, null)
    if (node.right === null) node.right = new Node([mid + 1, r], null, null)
    if (node.add) {
      node.left.v += node.add
      node.right.v += node.add
      node.left.add += node.add
      node.right.add += node.add
      node.add = 0
    }
  }
}
